040 - Get More Money（★7）

2つの状態への割り当て問題（燃やす埋める問題）→min cutで解ける

先に全ての現金を獲得しておき、「入らない→Ai円罰金　入る→W円罰金」というようにコストを定める。

つまり、入らない→家xに容量W, 家x→入るに容量A_xの辺を設定する。

また、「家dに入るには家c1,...,ckが必要」という制約は「家ciが入らない側かつ家dが入る側なものがあれば∞円罰金」と言い換えられる。つまり、入らない→ciとd→入るが両立してはいけない。ここから、ci→dへ容量∞の辺を貼る。

あとはこのグラフで最大流を流せばよい。